lectures.alex.balgavy.eu

Lecture notes from university.
git clone git://git.alex.balgavy.eu/lectures.alex.balgavy.eu.git
Log | Files | Refs | Submodules

Kruskal_s Algorithm.md (542B)

      1 +++
      2 title = "Kruskal's Algorithm"
      3 +++
      4 # Kruskal's Algorithm
      5 Used to find minimum spanning tree
      6 Faster in sparse graphs, does not need the graph to be connected.
      7 
      8 Steps:
      9 1. Removes all loops and parallel edges except one with least weight.
     10 2. Create edge table.
     11 3. Sort all the edges in increasing order of their weight.
     12 
     13 4. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
     14 
     15 5. Repeat step #4 until there are (V-1) edges in the spanning tree.